﻿
namespace LeetCode_Learn
{
    public class Part_01MargeSort
    {

        public static void Sort(int[] arr)
        {
            if (arr == null || arr.Length < 2) return;

            progress(arr, 0, arr.Length - 1);
        }

        static void progress(int[] arr, int left, int right)
        {
            if (left == right)
            {
                return;
            }
            int mid = left + ((right - left) >> 1);
            progress(arr, left, mid);
            progress(arr, mid + 1, right);
            marge(arr, left, right, mid);
        }

        static void marge(int[] arr, int left, int right, int mid)
        {

            int[] help = new int[right - left + 1];

            int i = 0;
            int p1 = left;
            int p2 = mid + 1;

            while (p1 <= mid && p2 <= right)
            {
                help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
            }

            while (p1 <= mid)
            {
                help[i++] = arr[p1++];
            }

            while (p2 <= right)
            {
                help[i++] = arr[p2++];
            }

            for (i = 0; i < right - left + 1; i++)
            {
                arr[left + i] = help[i];
            }
        }
    }
}
